package com.csx.base.core.algorithm.arr;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 *
 * <p>给定一个含有 n 个正整数的数组和一个正整数 target 。
 *
 * <p>找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，
 * 并返回其长度。如果不存在符合条件的子数组，返回 0
 *
 * <p>示例 1：
 * <p>输入：target = 7, nums = [2,3,1,2,4,3]
 * <p>输出：2
 * <p>解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 *
 * <p>示例 2：
 * <p>输入：target = 4, nums = [1,4,4]
 * <p>输出：1
 *
 * <p>示例 3：
 * <p>输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 * <p>输出：0
 *
 * @author cuisongxu
 * @date 2024/2/25 周日 11:43
 */
public class MinSubArrayLen {

    public static void main(String[] args) {
        MinSubArrayLen minSubArrayLen = new MinSubArrayLen();
//        int i = minSubArrayLen.minSubArrayLen(15, new int[]{1,2,3,4,5});
//        int i = minSubArrayLen.minSubArrayLen(213, new int[]{12,28,83,4,25,26,25,2,25,25,25,12});
        int i = minSubArrayLen.minSubArrayLen(15, new int[]{5,1,3,5,10,7,4,9,2,8});
        System.out.println(i);
    }

    /**
     * 滑动窗口
     * <p> 时间复杂度: O(n)
     * <p> 空间复杂度: O(n)
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        if(nums == null || nums.length < 1) {
            return 0;
        }

        int len = 0;
        int minLen = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            len ++;
            if(sum >= target) {
                // 只有更小的值才能更新
                if(minLen == 0 || minLen >= len) {
                    minLen = len;
                }
                // 从左开始减少数量,不断滑动窗口
                while(sum >= target) {
                    sum = sum - nums[i + 1 - len];
                    len --;
                }
                //
                if(minLen > len + 1) {
                    minLen = len + 1;
                }
            }
        }
        return minLen;
    }
}
